{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Set Mismatch"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #hash-table #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #哈希表 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findErrorNums"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #错误的集合"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>集合 <code>s</code> 包含从 <code>1</code> 到 <code>n</code> 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 <strong>丢失了一个数字</strong> 并且 <strong>有一个数字重复</strong> 。</p>\n",
    "\n",
    "<p>给定一个数组 <code>nums</code> 代表了集合 <code>S</code> 发生错误后的结果。</p>\n",
    "\n",
    "<p>请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,2,4]\n",
    "<strong>输出：</strong>[2,3]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,1]\n",
    "<strong>输出：</strong>[1,2]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 <= nums.length <= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 <= nums[i] <= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [set-mismatch](https://leetcode.cn/problems/set-mismatch/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [set-mismatch](https://leetcode.cn/problems/set-mismatch/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,2,4]', '[1,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "      for i in range(1, len(nums)+1):\n",
    "        try: nums.remove(i)\n",
    "        except: missed = i\n",
    "      return [nums[0], missed]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums):\n",
    "        ln = len(nums)\n",
    "        repeat = lose = -1\n",
    "        nums.sort()\n",
    "        if nums[0] != 1:\n",
    "            lose = 1\n",
    "        elif nums[-1] != ln:\n",
    "            lose = ln\n",
    "        for i in range(1, ln):\n",
    "            if nums[i] == nums[i - 1]:\n",
    "                repeat = nums[i]\n",
    "            if nums[i] - nums[i - 1] == 2:\n",
    "                lose = nums[i] - 1\n",
    "        return [repeat, lose]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if i+1 in nums:\n",
    "                nums.remove(i+1)\n",
    "            else:\n",
    "                res.append(i+1)\n",
    "        res.insert(0,nums[0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        m = [0] * len(nums)\n",
    "        for i in nums:\n",
    "            m[i - 1] += 1\n",
    "        rep = 0\n",
    "        lost = 0\n",
    "        for j in range(len(m)):\n",
    "            if m[j] == 2:\n",
    "                rep = j + 1\n",
    "            elif not m[j]:\n",
    "                lost = j + 1\n",
    "            if lost and rep:\n",
    "                return [rep, lost]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "n1 = 当前数组 - 去掉重复的数组和\n",
    "n2 = 原数组和 - 去掉重复的数组和\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        n1 = sum(nums)-sum(set(nums))\n",
    "        n2 = sum(range(len(nums)+1))-sum(set(nums))\n",
    "        return [n1,n2]\n",
    "\n",
    "# 作者：木子雨巷\n",
    "# 链接：https://leetcode.cn/problems/set-mismatch/solutions/562742/ji-bai-liao-10000-de-yong-hu-bi-xu-yao-j-po5j/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)-1):\n",
    "            if nums[i] ==  nums[i+1]:\n",
    "                res.append(nums[i])\n",
    "        for i in range(1,len(nums)+1):\n",
    "            if i not in nums:\n",
    "                res.append(i)        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            while nums[i] != i + 1 and nums[nums[i] - 1] != nums[i]:\n",
    "                tmp = nums[i]\n",
    "                nums[i] = nums[tmp - 1]\n",
    "                nums[tmp - 1] = tmp\n",
    "                #print(nums)\n",
    "        a, b = -1, -1\n",
    "        for i in range(n):\n",
    "            if nums[i] != i + 1:\n",
    "                a = nums[i]\n",
    "                b = i+1\n",
    "        return [a, b]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        nums=sorted(nums)\n",
    "        ans=[]\n",
    "        x=0\n",
    "        while x<len(nums)-1:\n",
    "            if nums[x]==nums[x+1]:\n",
    "                ans.append(nums[x])\n",
    "            x+=1\n",
    "        n=len(nums)\n",
    "        for x in range(1,n+1):\n",
    "            if x not in nums:\n",
    "                ans.append(x)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        nums = sorted(nums)\n",
    "        loss = 0\n",
    "        double = 0\n",
    "        prev = 0 # 记录遍历的前一个数，看两数之差是否为2\n",
    "        for i in range(len(nums)):\n",
    "            if i + 1 not in nums:\n",
    "                loss = i + 1\n",
    "            if double == 0:\n",
    "                if nums[i] == nums[i + 1]:\n",
    "                    double = nums[i]\n",
    "            if loss != 0 and double != 0:\n",
    "                break\n",
    "        return [double, loss]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = [0,0]\n",
    "        prev = 0\n",
    "        for i in range(0, n):\n",
    "            curr = nums[i]\n",
    "            if curr == prev:\n",
    "                ans[0] = prev\n",
    "            elif curr - prev > 1:\n",
    "                ans[1] = prev + 1\n",
    "            prev = curr\n",
    "        if nums[n - 1] != n:\n",
    "            ans[1] = n\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        nums.sort()\n",
    "        nums = [0] + nums\n",
    "        j, tmp = 1, 0\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i] == nums[i-1]:\n",
    "                tmp = nums[i]\n",
    "                if ans:\n",
    "                    break\n",
    "                else:\n",
    "                    continue\n",
    "            if nums[i] == j:\n",
    "                j += 1\n",
    "            else:\n",
    "                if tmp:\n",
    "                    ans.append(j)\n",
    "                    break\n",
    "                else:\n",
    "                    ans.append(j)\n",
    "                    j += 2\n",
    "        if len(nums)-1 != nums[-1]:\n",
    "            return [tmp, len(nums)-1]\n",
    "        return [tmp] + ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        lose = repeat = -1\n",
    "        n = len(nums)\n",
    "        #丢失首位1 末尾n需要单独考虑\n",
    "        if nums[0] != 1:\n",
    "            lose = 1\n",
    "        elif nums[-1] != n:\n",
    "            lose = n\n",
    "        #除去1、n剩下的数字直接用range(1,n)来辅助数组的判断\n",
    "        #重复和丢失的数字分别定位并判断\n",
    "        for i in range(1,n):\n",
    "            if nums[i] == nums[i-1]:\n",
    "                repeat = nums[i]\n",
    "            if nums[i] - nums[i-1] == 2:\n",
    "                lose = nums[i] - 1\n",
    "\n",
    "        return [repeat,lose]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        ans=[0,0]\n",
    "        nums.sort()\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i] == nums[i-1]:\n",
    "                ans[0] = nums[i]\n",
    "            \n",
    "            if i not in nums:\n",
    "                ans[1] = i \n",
    "            elif i+1 not in nums:\n",
    "                ans[1] = i+1         \n",
    "        return ans        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        ct = [0] * (len(nums)+2)\n",
    "        for num in nums:\n",
    "            ct[num] += 1\n",
    "        for i in range(1, len(nums)+1):\n",
    "            if ct[i] == 2:\n",
    "                ct[-1] = i\n",
    "            elif ct[i] == 0:\n",
    "                ct[0] = i\n",
    "        return [ct[-1],ct[0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        count = [0] * n\n",
    "\n",
    "        for num in nums:\n",
    "            count[num-1] += 1\n",
    "        \n",
    "        dup = -1\n",
    "        miss = -1\n",
    "        for i in range(0, n):\n",
    "            if count[i] == 0:\n",
    "                miss = i + 1\n",
    "            elif count[i] == 2:\n",
    "                dup = i + 1\n",
    "        return dup, miss"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            while nums[i] != i + 1 and nums[nums[i] - 1] != nums[i]:\n",
    "                tmp = nums[i]\n",
    "                nums[i] = nums[tmp - 1]\n",
    "                nums[tmp - 1] = tmp\n",
    "        a, b = -1, -1\n",
    "        for i in range(n):\n",
    "            if nums[i] != i + 1:\n",
    "                a = nums[i]\n",
    "                b = i+1\n",
    "        return [a, b]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        xor = 0\n",
    "        for num in nums:\n",
    "            xor ^= num\n",
    "        for i in range(1, n + 1):\n",
    "            xor ^= i\n",
    "        lowbit = xor & (-xor)\n",
    "        num1 = 0\n",
    "        num2 = 0\n",
    "        for num in nums:\n",
    "            if (num & lowbit) == 0:\n",
    "                num1 ^= num\n",
    "            else:\n",
    "                num2 ^= num\n",
    "        for i in range(1, n + 1):\n",
    "            if (i & lowbit) == 0:\n",
    "                num1 ^= i\n",
    "            else:\n",
    "                num2 ^= i\n",
    "        for num in nums:\n",
    "            if num == num1:\n",
    "                return [num1, num2]\n",
    "        return [num2, num1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            while nums[i] != i - 1:\n",
    "                if nums[i] == nums[nums[i] - 1]:\n",
    "                    break\n",
    "                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]\n",
    "        for i in range(n):\n",
    "            if nums[i] != i + 1:\n",
    "                return [nums[i], i + 1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            while nums[i] != i - 1:\n",
    "                if nums[i] == nums[nums[i] - 1]:\n",
    "                    break\n",
    "                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]\n",
    "        for i in range(n):\n",
    "            if nums[i] != i + 1:\n",
    "                return [nums[i], i + 1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums) + 1\n",
    "        count = [0] * n \n",
    "        sm = comb(n, 2)\n",
    "        for x in nums:\n",
    "            count[x] += 1\n",
    "            if count[x] == 2:\n",
    "                repeat = x\n",
    "            else:\n",
    "                sm -= x\n",
    "        return [repeat, sm]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        for i in range(1,n):\n",
    "            if nums[i] == nums[i-1]: return [nums[i], nums[i] - int(sum(nums)-(n+1)*n/2)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://mp.weixin.qq.com/s/o3GQ4fXjPkS04Sr9uPH8ZQ\n",
    "# 方法一：暴力\n",
    "# 其实很容易解决这个问题，先遍历一次数组，用一个哈希表记录每个数字出现的次数，然后遍历一次[1..N]，看看那个元素重复出现，那个元素没有出现，就 OK 了\n",
    "\n",
    "# # 方法二：\n",
    "# # 先假设集合nums里面是0到n-1的数，索引也是0到n-1。也就是索引和数字一一对应\n",
    "# class Solution:\n",
    "#     def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "#         n = len(nums)\n",
    "#         dup = -1\n",
    "#         for i in range(n):\n",
    "#             idx = abs(nums[i])\n",
    "#             if nums[idx] < 0:\n",
    "#                 # 如果nums[index]小于0，则说明重复访问 \n",
    "#                 # 既然idx对应的数是负数，那这个duplicate的数肯定是nums[i]了\n",
    "#                 dup = abs(nums[i])\n",
    "#             else:\n",
    "#                 # 最终是想把nums[idx]的数全部变为负数\n",
    "#                 nums[idx] *= -1\n",
    "        \n",
    "#         missing = -1\n",
    "#         for i in range(n):\n",
    "#             if nums[i] > 0:\n",
    "#                 # 如果nums[i]大于0，则说明没有访问  \n",
    "#                 missing = nums[i]\n",
    "#                 break\n",
    "        \n",
    "#         return [dup, missing]\n",
    "\n",
    "\n",
    "# 方法二：\n",
    "# 对上述的修改，整数范围变为1到n。但索引范围是0到n-1.所以num对应的索引应该是num-1\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        dup = -1\n",
    "        for i in range(n):\n",
    "            # 索引从0开始\n",
    "            idx = abs(nums[i]) - 1\n",
    "            if nums[idx] < 0:\n",
    "                # 如果nums[index]小于0，则说明重复访问 \n",
    "                # 既然idx对应的数是负数，那这个duplicate的数肯定是nums[i]了\n",
    "                dup = abs(nums[i])\n",
    "            else:\n",
    "                # 最终是想把nums[idx]的数全部变为负数\n",
    "                nums[idx] *= -1\n",
    "        \n",
    "        \n",
    "        missing = -1\n",
    "        for i in range(n):\n",
    "            if nums[i] > 0:\n",
    "                # 如果nums[i]大于0，则说明没有访问\n",
    "                # 将索引转换成元素。经过上一步的转换，nums[i]对应的元素变成了对应的idx\n",
    "                # 而这个idx对应的元素，因为元素范围是1到n，所以idx+1=元素\n",
    "                missing = i + 1\n",
    "                break\n",
    "        \n",
    "        return [dup, missing]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        dup = -1\n",
    "        for i in range(n):\n",
    "            # 索引应该从0开始\n",
    "            index = abs(nums[i]) - 1\n",
    "            # nums[index]小于0则说明重复访问 \n",
    "            if nums[index] < 0:\n",
    "                dup = abs(nums[i])\n",
    "            else:\n",
    "                nums[index] *= -1\n",
    "        missing = -1\n",
    "        for i in range(n):\n",
    "            # nums[i]大于0则说明没有访问 \n",
    "            if nums[i] > 0:\n",
    "                # 将索引转换成元素 \n",
    "                missing = i + 1\n",
    "        return dup, missing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://mp.weixin.qq.com/s/o3GQ4fXjPkS04Sr9uPH8ZQ\n",
    "# 方法一：暴力\n",
    "# 其实很容易解决这个问题，先遍历一次数组，用一个哈希表记录每个数字出现的次数，然后遍历一次[1..N]，看看那个元素重复出现，那个元素没有出现，就 OK 了\n",
    "\n",
    "# # 方法二：\n",
    "# # 先假设集合nums里面是0到n-1的数，索引也是0到n-1。也就是索引和数字一一对应\n",
    "# class Solution:\n",
    "#     def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "#         n = len(nums)\n",
    "#         dup = -1\n",
    "#         for i in range(n):\n",
    "#             idx = abs(nums[i])\n",
    "#             if nums[idx] < 0:\n",
    "#                 # 如果nums[index]小于0，则说明重复访问 \n",
    "#                 # 既然idx对应的数是负数，那这个duplicate的数肯定是nums[i]了\n",
    "#                 dup = abs(nums[i])\n",
    "#             else:\n",
    "#                 # 最终是想把nums[idx]的数全部变为负数\n",
    "#                 nums[idx] *= -1\n",
    "        \n",
    "#         missing = -1\n",
    "#         for i in range(n):\n",
    "#             if nums[i] > 0:\n",
    "#                 # 如果nums[i]大于0，则说明没有访问  \n",
    "#                 missing = nums[i]\n",
    "#                 break\n",
    "        \n",
    "#         return [dup, missing]\n",
    "\n",
    "\n",
    "# 方法二：\n",
    "# 对上述的修改，整数范围变为1到n。但索引范围是0到n-1.所以num对应的索引应该是num-1\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        dup = -1\n",
    "        for i in range(n):\n",
    "            # 索引从0开始\n",
    "            idx = abs(nums[i]) - 1\n",
    "            if nums[idx] < 0:\n",
    "                # 如果nums[index]小于0，则说明重复访问 \n",
    "                # 既然idx对应的数是负数，那这个duplicate的数肯定是nums[i]了\n",
    "                dup = abs(nums[i])\n",
    "            else:\n",
    "                # 最终是想把nums[idx]的数全部变为负数\n",
    "                nums[idx] *= -1\n",
    "        \n",
    "        \n",
    "        missing = -1\n",
    "        for i in range(n):\n",
    "            if nums[i] > 0:\n",
    "                # 如果nums[i]大于0，则说明没有访问\n",
    "                # 将索引转换成元素。经过上一步的转换，nums[i]对应的元素变成了对应的idx\n",
    "                # 而这个idx对应的元素，因为元素范围是1到n，所以idx+1=元素\n",
    "                missing = i + 1\n",
    "                break\n",
    "        \n",
    "        return [dup, missing]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        sum1 = (n * (n + 1)) // 2\n",
    "        sub = sum1 - sum(nums)\n",
    "        nums.sort()\n",
    "        for i in range(n-1):\n",
    "            if nums[i] == nums[i+1]:\n",
    "                re = nums[i]\n",
    "                break\n",
    "        ans = [re]\n",
    "        ans.append(re + sub)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        nums = sorted(nums)\n",
    "        re = [0,0]\n",
    "        for i in range(len(nums)):\n",
    "            if i+1 not in nums:\n",
    "                re[1] = i+1\n",
    "            if i>0 and nums[i]==nums[i-1]:\n",
    "                re[0] = nums[i]\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        map=[0]*(n+1)\n",
    "        res=[0]*2\n",
    "        for num in nums:\n",
    "            map[num]+=1\n",
    "        for i in range(1,n+1):\n",
    "            if map[i]==0:\n",
    "                res[1]=i\n",
    "            elif map[i]==2:\n",
    "                res[0]=i\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        \n",
    "        if int(n * (n + 1)/2) > sum(nums):\n",
    "            false = [v for i, v in enumerate(nums) if i + 1 != v][0]\n",
    "            return [false, false + int(n * (n + 1)/2) - sum(nums)]\n",
    "        else:\n",
    "            false = [i + 1 for i, v in enumerate(nums) if i + 1 != v][0]\n",
    "            return [false - int(n * (n + 1)/2) + sum(nums), false]\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "#最适合这个题目的 字典dict (使用Counter可以把数组array转换为字典dict)\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        dic = Counter(nums)\n",
    "        n = len(nums)\n",
    "        repeat = lose = -1\n",
    "        #没有在dict中找到的数字为lose\n",
    "        #找到的数字value为2的便是repeat\n",
    "        for i in range(1,n+1):\n",
    "            tmp = dic.get(i,0)\n",
    "            if tmp == 0:\n",
    "                lose = i\n",
    "            elif tmp == 2:\n",
    "                repeat = i\n",
    "        \n",
    "        return [repeat,lose]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "\n",
    "        num_freq = defaultdict(int)\n",
    "        for x in nums:\n",
    "            num_freq[x] += 1\n",
    "        \n",
    "        a, b = -1, -1\n",
    "        for x in range(1, n + 1):\n",
    "            f = num_freq[x]\n",
    "            if f == 2:\n",
    "                a = x\n",
    "            if f == 0:\n",
    "                b = x\n",
    "                \n",
    "        return [a, b]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        errorNums=[0,0]\n",
    "        mp={}\n",
    "        for i in nums:\n",
    "            \n",
    "            if i not in mp:\n",
    "                mp[i]=1\n",
    "            else:\n",
    "                mp[i]+=1\n",
    "        for j in range(1,len(nums)+1):\n",
    "            if j not in mp:\n",
    "                errorNums[1]=j\n",
    "            else:\n",
    "                if mp[j]==2:\n",
    "                    errorNums[0]=j\n",
    "            \n",
    "        return errorNums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        dic = {}\n",
    "        for i in nums:\n",
    "            if i not in dic:\n",
    "                dic[i] = 1\n",
    "            else:\n",
    "                ans.append(i)\n",
    "                \n",
    "        for i in range(1, len(nums) + 1):\n",
    "            if i not in dic:\n",
    "                ans.append(i)\n",
    "                \n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        c=Counter(nums)\n",
    "        l=[0,0]\n",
    "        for i in range(1,max(nums)+1):\n",
    "            if c[i]>=2:\n",
    "                l[0]=i\n",
    "            elif c[i]==0:\n",
    "                l[1]=i\n",
    "        if l[1]==0:\n",
    "            return [l[0],max(nums)+1]\n",
    "        else:\n",
    "            return l\n",
    "            \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        hash = {}\n",
    "        for n in nums:\n",
    "            hash[n] = hash.get(n,0)+1\n",
    "        dup = None\n",
    "\n",
    "        for k, v in hash.items():\n",
    "            if v==2:\n",
    "                dup = k\n",
    "                break\n",
    "        for i in range(1, len(nums)+1):\n",
    "            if i not in hash:\n",
    "                miss = i\n",
    "                break\n",
    "        return dup, miss"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        total=sum(range(1,len(nums)+1))\n",
    "        num=total-sum(set(nums))\n",
    "        diff=total-sum(nums)\n",
    "        return [num-diff,num]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        total = sum(range(1,len(nums)+1))\n",
    "        num = total - sum(set(nums))\n",
    "        diff = total - sum(nums)\n",
    "        return [num-diff,num]\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    ## 思路：1. 排序； 2. 找到重复值； 3. 对nums求和，减去按公式求出的和，所得的差值就是重复的数比缺失数字多出来（或者少掉）的部分； 4. 用重复数字减去这个差值，得到的就是缺失数字的值.\n",
    "\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "\n",
    "        # 这里实现一个归并排序\n",
    "        def merge(lst1, lst2): # 功能：实现归并。比较两个列表中元素的大小，然后依次加入新列表中\n",
    "            res = []\n",
    "            i, j = 0, 0\n",
    "            while i < len(lst1) and j <len(lst2):\n",
    "                if lst1[i] < lst2[j]:\n",
    "                    res.append(lst1[i])\n",
    "                    i += 1\n",
    "                else:\n",
    "                    res.append(lst2[j])\n",
    "                    j += 1\n",
    "            if i == len(lst1):\n",
    "                res += lst2[j:]\n",
    "            else: res += lst1[i:]\n",
    "            return res\n",
    "        \n",
    "        def merge_sort(lst): # 功能：实现归并排序。将列表从中间分成左右两部分，依次实现归并排序，然后合并。\n",
    "            if len(lst) <= 1: return lst\n",
    "            mid = len(lst)//2\n",
    "            l = merge_sort(lst[:mid])\n",
    "            r = merge_sort(lst[mid:])\n",
    "            return merge(l,r)\n",
    "        n = len(nums)\n",
    "        #nums.sort()\n",
    "        nums = merge_sort(nums)\n",
    "        for i in range(1,n):\n",
    "            if nums[i] == nums[i-1]: return [nums[i], nums[i] - int(sum(nums)-(n+1)*n/2)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        a = {}\n",
    "        ans = [0, 0]\n",
    "\n",
    "        for num in nums:\n",
    "            a[num] = a.get(num, 0) + 1\n",
    "        \n",
    "        for j in range(n + 1):\n",
    "            count = a.get(j, 0)\n",
    "            if count == 2:\n",
    "                ans[0] = j\n",
    "            elif count == 0:\n",
    "                ans[1] = j\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        ans = list()\n",
    "        note = dict()\n",
    "\n",
    "        for num in nums:\n",
    "            if num not in note:\n",
    "                note[num] = True\n",
    "            else:\n",
    "                ans.append(num)\n",
    "\n",
    "        for i in range(1, len(nums) + 1):\n",
    "            if i not in note:\n",
    "                ans.append(i)\n",
    "\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        # 重复：集合差集\n",
    "        # 缺失：创建1-n集合，再差集\n",
    "        res = []\n",
    "        dic = {}\n",
    "        for i in nums:\n",
    "            if i not in dic.keys():\n",
    "                dic[i] = 1\n",
    "            else:\n",
    "                res.append(i)\n",
    "        rightList = [x for x in range(1, len(nums)+1)]\n",
    "        # print(rightList)\n",
    "        for j in range(len(rightList)):\n",
    "            if rightList[j] not in dic.keys():\n",
    "                res.append(rightList[j])\n",
    "            else:\n",
    "                dic[rightList[j]] -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        my_dict = dict.fromkeys(range(1, n+1), 0)\n",
    "        miss_val, repeat_val = 0, 0\n",
    "        for i in range(n):\n",
    "            my_dict[nums[i]] += 1\n",
    "        for i in range(1, n+1):\n",
    "            if my_dict[i] == 2:\n",
    "                repeat_val = i\n",
    "            elif my_dict[i] == 0:\n",
    "                miss_val = i\n",
    "        return [repeat_val, miss_val]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        m = set()\n",
    "        t = 0\n",
    "        r = 0\n",
    "        for idx, n in enumerate(nums):\n",
    "            t ^= idx + 1\n",
    "            if n in m:\n",
    "                r = n\n",
    "                continue\n",
    "            m.add(n)\n",
    "            t ^= n\n",
    "        return [r, t]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        a = sum(nums) - sum(set(nums))\n",
    "        b = sum(range(len(nums)+1)) - sum(set(nums))\n",
    "        return [a,b]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        dic = Counter(nums)\n",
    "        \n",
    "        repeat = -1\n",
    "        lose = -1\n",
    "\n",
    "        for i in range(1,len(nums)+1):\n",
    "            tmp = dic.get(i,0)\n",
    "            if tmp ==0:\n",
    "                lose = i\n",
    "            elif tmp==2:\n",
    "                repeat=i\n",
    "        return [repeat,lose]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        n,pure=len(nums),sum(set(nums))\n",
    "        return [sum(nums)-pure,(1+n)*n//2-pure]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        double_xor = 0\n",
    "        num_dic = set()\n",
    "        for idx,val in enumerate(nums):\n",
    "            double_xor ^= (idx+1)\n",
    "            double_xor ^= val\n",
    "            if val in num_dic:\n",
    "                doubled_num = val\n",
    "            else:\n",
    "                num_dic.add(val)\n",
    "        return [doubled_num, double_xor^doubled_num ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        total = sum(range(1,len(nums)+1))\n",
    "        num = total - sum(set(nums))\n",
    "        diff = total - sum(nums)\n",
    "        return [num-diff,num]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        b = sum(list(range(1,len(nums)+1))) - sum(set(nums))\n",
    "        a = sum(nums) - sum(set(nums))\n",
    "        return [a,b]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        all_num = [i for i in range(1,len(nums)+1)]\n",
    "        res = {}\n",
    "        re_num = None\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] in res:\n",
    "                re_num = nums[i]\n",
    "            else:\n",
    "                res[nums[i]] = i\n",
    "                all_num.remove(nums[i])\n",
    "        return [re_num, all_num[0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        total = sum(range(1, n+1))\n",
    "        numsTotal = sum(set(nums))\n",
    "        return [sum(nums)-numsTotal, total-numsTotal]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        #法1 重复：集合差集，通过求和之差表示\n",
    "        #法1 缺失：1-n的总和 - 去重后的数组和\n",
    "        ans = []\n",
    "        ans.append(sum(nums) - sum(set(nums)))\n",
    "        ans.append(((1+ len(nums))* (len(nums))) // 2 - sum(set(nums)))\n",
    "        return ans\n",
    "        #法2 字典（哈希表）\n",
    "        # res = []\n",
    "        # dic = {}\n",
    "        # for i in nums:\n",
    "        #     if i not in dic.keys():\n",
    "        #         dic[i] = 1\n",
    "        #     else:\n",
    "        #         res.append(i)\n",
    "        # rightList = [x for x in range(1, len(nums)+1)]\n",
    "        # # print(rightList)\n",
    "        # for j in range(len(rightList)):\n",
    "        #     if rightList[j] not in dic.keys():\n",
    "        #         res.append(rightList[j])\n",
    "        #     else:\n",
    "        #         dic[rightList[j]] -= 1\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        exp_sum=sum(range(1,n+1))\n",
    "        set_sum=sum(set(nums))\n",
    "        rea_sum=sum(nums)\n",
    "        repeat_ele=rea_sum-set_sum\n",
    "        missing_ele=exp_sum-set_sum\n",
    "        return [repeat_ele,missing_ele]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\r\n",
    "class Solution:\r\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\r\n",
    "        n = len(nums)\r\n",
    "        target_sum = (1 + n) * n // 2\r\n",
    "        visited = set()\r\n",
    "        res = []\r\n",
    "        for num in nums:\r\n",
    "            if num in visited:\r\n",
    "                res.append(num)\r\n",
    "                break\r\n",
    "            visited.add(num)\r\n",
    "\r\n",
    "        res.append(res[0] + (target_sum - sum(nums)))\r\n",
    "        return res\r\n",
    "            \r\n",
    "            \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        size = nums.__len__()\n",
    "        unique_sum = sum([i for i in range(1, size+1)])\n",
    "        set_sum = sum(set(nums))\n",
    "        total_sum = sum(nums)\n",
    "        duplicated_num = total_sum - set_sum\n",
    "        missing_num = unique_sum - set_sum\n",
    "        return [duplicated_num, missing_num]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        n = len(nums)\n",
    "        expected_sum = n * (n + 1) // 2\n",
    "        a = sum(nums)\n",
    "        nums = set(nums)\n",
    "        b = sum(nums)\n",
    "        x = a - b\n",
    "        res.append(x)\n",
    "        y = expected_sum - b\n",
    "        res.append(y)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        su = (1+n)*n//2\n",
    "        k = su - sum(set(nums))\n",
    "        return [i for i in set(nums) if nums.count(i)>1] + [k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        res = [0] * 2\n",
    "        for i in range(len(nums)-1):\n",
    "            if nums[i] == nums[i+1]:\n",
    "                res[0] = nums[i]\n",
    "\n",
    "        nums = sorted(list(set(nums)))\n",
    "        for i in range(len(nums)):\n",
    "            if i + 1 != nums[i]:\n",
    "                res[1] = i + 1\n",
    "                break\n",
    "        if res[1] == 0:\n",
    "            res[1] = len(nums) + 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        oriSum = (1+len(nums))*len(nums)/2\n",
    "        nowSum = sum(nums)\n",
    "\n",
    "        numsDict = Counter(nums)\n",
    "        numsDict = sorted(numsDict.items(), key = lambda x: -x[1])\n",
    "        res.append(numsDict[0][0])\n",
    "        res.append(int(numsDict[0][0] + oriSum - nowSum))\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        from collections import Counter\n",
    "        list_sx=[0]*len(nums)\n",
    "        for i in range(1,len(nums)+1):\n",
    "            list_sx[i-1]=i\n",
    "        zd3=Counter(list_sx)-Counter(nums)\n",
    "        a2=0\n",
    "        for key in zd3.keys():\n",
    "            a2=key\n",
    "        return [sum(nums)-sum(set(nums)),a2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        hash_map = {}\n",
    "        res = []\n",
    "        for i in nums:\n",
    "            hash_map[i] = hash_map.get(i, 0) + 1\n",
    "        for k, v in hash_map.items():\n",
    "            if v == 2:\n",
    "                res.append(k)\n",
    "        y = sum(range(1, len(nums) + 1))\n",
    "        s = sum(set(nums))\n",
    "        res.append(y - s)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        from collections import Counter\n",
    "        list_sx=[0]*len(nums)\n",
    "        duibi=[0]*len(nums)\n",
    "        a1=0\n",
    "        for i in range(1,len(nums)+1):\n",
    "            list_sx[i-1]=i\n",
    "            if nums[i-1] in duibi:\n",
    "                a1=nums[i-1]\n",
    "            duibi[i-1]=nums[i-1]\n",
    "        zd1=Counter(list_sx)\n",
    "        zd2=Counter(duibi)\n",
    "        zd3=zd1-zd2\n",
    "        a2=0\n",
    "        for key in zd3.keys():\n",
    "            a2=key\n",
    "        return [a1,a2]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        from collections import Counter\n",
    "        list_sx=[0]*len(nums)\n",
    "        duibi=[0]*len(nums)\n",
    "        a1=0\n",
    "        for i in range(1,len(nums)+1):\n",
    "            list_sx[i-1]=i\n",
    "            if nums[i-1] in duibi:\n",
    "                a1=nums[i-1]\n",
    "            duibi[i-1]=nums[i-1]\n",
    "        zd3=Counter(list_sx)-Counter(duibi)\n",
    "        a2=0\n",
    "        for key in zd3.keys():\n",
    "            a2=key\n",
    "        return [a1,a2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        ans = [0,0]\n",
    "        res = set([i for i in range(1,len(nums)+1)])\n",
    "        for i in range(1,len(nums)+1):\n",
    "            if i in nums:\n",
    "                nums.remove(i)\n",
    "            else:\n",
    "                ans[1] = i\n",
    "        ans[0] = nums[-1]\n",
    "        return ans\n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        from collections import Counter\n",
    "        nums_cnt=Counter(nums)\n",
    "        for ele in nums_cnt.items():\n",
    "            if ele[1]==2:\n",
    "                res=ele[0]\n",
    "        n=len(nums)\n",
    "        exp_sum=sum(range(1,n+1))\n",
    "        rea_sum=sum(set(nums))\n",
    "        if exp_sum>rea_sum:\n",
    "            return [res,exp_sum-rea_sum]\n",
    "        else:\n",
    "            return [res,rea_sum-exp_sum]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        ans=[]\n",
    "        from collections import Counter\n",
    "        a=Counter(nums)\n",
    "        for i in a:\n",
    "            if a[i]==2:\n",
    "                ans.append(i)\n",
    "        n=[i for i in range(1,len(nums)+1)]\n",
    "        c=set(nums)\n",
    "        for j in c:\n",
    "            n.remove(j)\n",
    "        ans.extend(n)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        dic={}\n",
    "        res=[]\n",
    "        for i in nums:\n",
    "            dic[i]=dic.get(i,0)+1\n",
    "        for key,value in dic.items():\n",
    "            if value==2:\n",
    "                res.append(key)\n",
    "        whole=[]\n",
    "        for  i in range(1,len(nums)+1):\n",
    "            whole.append(i)\n",
    "        # 1-n 作为一个列表，nums 去重再转为列表，这俩的和的差就是丢失的数字\n",
    "        miss=sum(whole)-sum(list(set(nums)))\n",
    "        res.append(miss)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        before=[]\n",
    "        up=0\n",
    "        lack=None\n",
    "        for i in nums:\n",
    "            if i in before:\n",
    "                repeat=i\n",
    "                break\n",
    "            else:\n",
    "                before.append(i)\n",
    "        lack=list(set(range(1, len(nums)+1))-set(nums))[0]\n",
    "        return [repeat,lack]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        a=list(range(1,len(nums)+1))\n",
    "        b=list(set(a)-set(nums))\n",
    "        b.append(b[0]-sum(a)+sum(nums))\n",
    "        return b[::-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        a = set()\n",
    "        b = set(nums)\n",
    "        for i in range(1, n+1):\n",
    "            if i not in b:\n",
    "                break\n",
    "        for j in nums:\n",
    "            if j not in a:\n",
    "                a.add(j)\n",
    "            else:\n",
    "                break\n",
    "        return [j, i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        repeat = 0\n",
    "        for x, y in Counter(nums).items():\n",
    "            if y == 2:\n",
    "                repeat = x\n",
    "                break\n",
    "        \n",
    "        lost = list(set(range(1, len(nums) + 1)) - set(nums))\n",
    "\n",
    "        return [repeat, lost[0]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        loss = list(set(x for x in range(1,n+1)) - set(nums))\n",
    "        h = {}\n",
    "        dupli = 0\n",
    "        for x in nums:\n",
    "            if x in h:\n",
    "                dupli = x\n",
    "                break\n",
    "            else:\n",
    "                h[x] = 1\n",
    "        res = []\n",
    "        res.append(dupli)\n",
    "        res += loss\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        # s1=set(s for s in range(1,len(nums)+1))\n",
    "        \n",
    "\n",
    "        return [[i for i,j in collections.Counter(nums).items() if j !=1][0], list(set(s for s in range(1,len(nums)+1))-set(nums))[0]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        before=[]\n",
    "        up=0\n",
    "        lack=None\n",
    "        for i in nums:\n",
    "            if i in before:\n",
    "                repeat=i\n",
    "                break\n",
    "            else:\n",
    "                before.append(i)\n",
    "        lack=list(set(range(1, len(nums)+1))-set(nums))[0]\n",
    "        return [repeat,lack]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        L=list(collections.Counter(nums).items())\n",
    "        assi=True\n",
    "        U = [i for i in range(1,len(nums)+1)]\n",
    "        for key,value in L:\n",
    "            if value==2:\n",
    "                dupli = key\n",
    "            U.remove(key)\n",
    "        res = []\n",
    "        res.append(dupli)\n",
    "        res+=U\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        tmp1 = set(nums)\n",
    "        tmp2 = set(list(range(1, len(nums)+1)))\n",
    "        res =  tmp2 - tmp1\n",
    "        for i in range(len(nums)-1):\n",
    "            if nums[i] == nums[i+1]:\n",
    "                return nums[i], *res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        n=list(set(range(1,len(nums)+1))-set(nums))[0]\n",
    "        m=[x for  x  in nums  if  nums.count(x)==2][0]\n",
    "        return  [m,n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        print(nums)\n",
    "        if len(nums) <= 1:\n",
    "            return []\n",
    "        set1 = set()\n",
    "        for i in range(1,len(nums)+1):\n",
    "            set1.add(i)\n",
    "        element = set1 - set(nums)\n",
    "        print(element)\n",
    "        result = None\n",
    "        i = 0\n",
    "        while i < len(nums) - 1:\n",
    "            if nums[i] == nums[i + 1]:\n",
    "                result = nums[i]\n",
    "                break\n",
    "            i += 1\n",
    "        print(i)\n",
    "        print(element)\n",
    "        return [result, element.pop()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        modal = [i for i in range(1,len(nums)+1)]\n",
    "        for i in nums:\n",
    "            if nums.count(i)>1:\n",
    "                res.append(i)\n",
    "                break\n",
    "        res.append(list(set(modal)-set(nums))[0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        # 20230813 2022-2030  虽然写出来了，但是感觉怪怪的？\n",
    "        dic = dict()\n",
    "        a = set([i+1 for i in range(len(nums))])\n",
    "        for num in nums:\n",
    "            if dic.get(num):\n",
    "                repeat_one = num\n",
    "            else:\n",
    "                dic[num] = 1\n",
    "                a.remove(num)\n",
    "        for item in a:\n",
    "            return [repeat_one, item]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findErrorNums(self, nums: List[int]) -> List[int]:\n",
    "        a = Counter(nums)\n",
    "        result = []\n",
    "        for i,ch in a.items():\n",
    "            if ch == 2:\n",
    "                result.append(i)\n",
    "        b = set(list(range(1,len(nums) + 1))) - set(nums)\n",
    "        result.append(list(b)[0])\n",
    "        return result"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
